// @algorithm @lc id=5 lang=cpp
// @title longest-palindromic-substring

#include <iostream>
#include <vector>
#include <string>
#include "algm/algm.h"
using namespace std;
// @test("babad")="bab"
// @test("cbbd")="bb"
// @test("abb")="bb"
// @test("a")="a"
// @test("aabbccdd")="aa"
// @test("aabbccddeddccbbaa")="aabbccddeddccbbaa"
// @test("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb")="bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

/**
 * @brief
 * 可以枚举回文中心并向两边扩展,
 * 如果两边的字母相同，我们就可以继续扩展，如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。
 */
class Solution {
public:
    string longestPalindrome(string s)
    {
        int len = s.size();
        int k, res = -1, res_i = 0, res_j = 0;

        for (int i = 0; i < len; i++) {
            //找到以下标i为中心的最长回文串
            for (k = 1; i - k >= 0 && i + k < len && s[i - k] == s[i + k]; k++)
                ;
            if ((--k) * 2 + 1 > res) {
                res   = k * 2 + 1;
                res_i = i - k;
                res_j = i + k;
            }

            //找到以下标i和下标i+1为中心的最长回文串
            if (i + 1 >= len || s[i] != s[i + 1])
                continue;
            for (k = 1; i - k >= 0 && i + 1 + k < len && s[i - k] == s[i + 1 + k]; k++)
                ;
            if ((--k) * 2 + 2 > res) {
                res   = k * 2 + 2;
                res_i = i - k;
                res_j = i + 1 + k;
            }
        }

        return s.substr(res_i, res_j - res_i + 1);
    }
};